package leetcode4;

import java.util.List;

class ListNode{
    int val;
    ListNode next;
}
public class Day5 {




    //回文链表

    public boolean isPalindrome(ListNode head) {
        if(head == null) return true;
        //1.找中间节点
        //2.反转后半部分链表
        //3.双指针判断是否回文
        //4.恢复后半部分链表

        ListNode mid = middleNode(head);
        ListNode headRight = reverseList(mid.next);

        ListNode left = head, right = headRight; //双指针
        boolean result = true;
        while(result && right != null) {
            if(left.val != right.val) {
                result = false;
            }
            left = left.next;
            right = right.next;
        }

        mid.next = reverseList(headRight);
        return result;
    }
    //反转链表，不需要虚拟头节点
    public ListNode reverseList(ListNode head) {
        ListNode prev = null; //标记新头
        while(head != null) {
            ListNode next = head.next; //2.1 记录下一个节点
            head.next = prev; //2.2 当前节点 链接 头结点下一个
            prev = head; //2.3 头节点 链接 当前节点
            head = next;
        }
        return prev;
    }

    //找链表中间节点
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next!=null) { //保证有三个节点
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow; //如果只有两个结点，就返回第一个节点
    }
}
